#include <stdio.h>
#include <malloc.h>

int max(int a, int b)
{
    if (a > b) return a;
    else return b;
}
int min(int a, int b)
{
    if (a < b) return a;
    else return b;
}
void build(int* a, int* t, int v, int tl, int tr)
{
    if (tl == tr)
        t[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        build(a, t, 2*v    , tl    , tm);
        build(a, t, 2*v + 1, tm + 1, tr);
        t[v] = t[2*v] + t[2*v + 1];
    }
}
int sum   (int* t, int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if(l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum(t, 2*v  ,tl    , tm, l         , min(r, tm)) +
           sum(t, 2*v+1,tm + 1, tr, max(l, tm+1), r);
}
void update(int* t, int v, int tl, int tr, int pos, int new_value)
{
    if (tl == tr)
        t[v] = new_value;
    else
    {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(t, 2*v, tl, tm, pos, new_value);
        else
            update(t, 2*v + 1, tm + 1, tr, pos, new_value);
        t[v] = t[2*v] + t[2*v + 1];
    }
}
int main()
{
    int n = 10;
    int* a = (int*) calloc(n, sizeof(int));
    int* t = (int*) calloc(4 * n, sizeof(int));

    for (int i = 1; i < n + 1; a[i] = i++);

    build(a, t, 1, 0, n - 1);
    for(int i = 0; i < 4*n; printf("%d ", *(t+i++)));
    printf("\n%d\n", sum(t, 1, 0, n-1, 5, 8));
    update(t, 1, 0, n - 1, 8, 80);
    printf("\n%d", sum(t, 1, 0, n-1, 5, 8));
    update(t, 1, 0, n - 1, 9, 10);
    printf("\n%d", sum(t, 1, 0, n-1, 5, 8));
    return 0;
}
